/***************************************************************************
                          mstl.h  -  Mini-STL library
                             -------------------
    begin                : Mon May 6 2002
    copyright            : (C) 2002 by Michiel Visser
    email                :
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/

//---------------------------------------------------------------------------
#ifndef __MSTL_H__
#define __MSTL_H__
//---------------------------------------------------------------------------

#include <mstl_alloc.h>

//#define inline __inline__ __attribute__((always_inline))

namespace MSTL
{
  
/*/// placement new operator (uses existing memory pointed by ptr).
inline void * operator new   (size_t, void *ptr)  { return ptr; }
/// placement new[] operator (uses existing memory pointed by ptr).
inline void * operator new[] ( size_t, void *ptr)  { return ptr; }
*/
//inline static void * operator new   ( size_t s)  { return ::new char[s]; }

/// Classes for data holders, pointers, vectors, lists(see \ref List ), etc.

#define TT template<class T>
#define TS template<class S>
#define TTS template<class T, class S>

//----- data holders -----

template<typename T, int S=sizeof(T)> class NoDeleteHolder // does not delete
{
protected:
   char dat[S];
   T &item() const { return *((T *)dat); }
public:
   operator T &() const { return item(); } // data itself
   operator const T &() const { return item(); } // data itself
   operator T *() const { return &item(); }
   operator const T *() const { return &item(); }
   operator void *() { return (void *)dat; } // space for data
   T &operator*() const { return item(); }
   T *operator->() const { return &item(); }
   void memCopyTo(void *target) const { memcpy(target, (void *)dat, S); }
   NoDeleteHolder() {}
   NoDeleteHolder(const T & cpyFrom) { Create<T>::fromSpace((void *)dat,cpyFrom); }
   NoDeleteHolder(const NoDeleteHolder & cpyFrom) { Create<T>::fromSpace((void *)dat,cpyFrom.item()); }
   typedef T Type;
   enum { Size=S };
};

// holds objects and subclasses of objects:
template<typename T, int S=sizeof(T)> class InheritanceHolder: public NoDeleteHolder<T,S>
{
public:
   InheritanceHolder() {}
   InheritanceHolder(const T & cpyFrom): NoDeleteHolder<T,S>(cpyFrom) {}
   InheritanceHolder(const InheritanceHolder & cpyFrom): NoDeleteHolder<T,S>(cpyFrom) {}
   inline ~InheritanceHolder() { ((T *)this->dat)->~T();}
};

struct Empty
{
   Empty() {}
};

class DynamicDuplicable
{
public:
   /// see #define MSTL_IMPL_DUPLICATE for implementation
   //virtual void *duplicate(int reservedheadersize) const;
   DynamicDuplicable() {}
   virtual int sizeOf() const;
   virtual void duplicateIn(void *space) const;
   virtual ~DynamicDuplicable();
};

/** holds the memory of an object of class T, which should be created with:
 * "Holder<T> h; new (h.space()) T( param1, param2, ...);"
 * The holder casts automatically to class T.
 * It calls the destructor at deletion.
 */

template<typename T, typename I=Empty> class Holder
{
public:
   I hdr;
private:
   char dat[sizeof(T)];
protected:
   T &item() const { return *((T *)dat); }
public:
   operator T &() const { return item(); } // data itself
   operator T *() const { return &item(); } // data itself
   operator const T *() const { return &item(); } // data itself
   operator const T &() const { return item(); } // data itself
   void *space() { return (void *)dat; } // space for data
   Holder() {}
   Holder(const T & cpyFrom)                         { Create<T>::fromSpace(space(),cpyFrom); }
   Holder(const Holder & cpyFrom) : hdr(cpyFrom.hdr) { Create<T>::fromSpace(space(),cpyFrom.item()); }
   Holder(const I & cpyFrom)      : hdr(cpyFrom)     {} // copy with same hdr
   Holder *duplicate() { void *p=reserveBytes<Holder>(sizeof(I)+item().sizeOf()); duplicateIn(p); return (Holder *)p; }
   void duplicateIn(void *p) { Create<Holder>::fromSpace(p); item().duplicateIn((I *)p+1); }
   inline ~Holder();  
   typedef T Type;
//internal:
  #define MSTL_IMPL_DUPLICATEIN(T) \
  void duplicateIn(void *space) const { new (space) T(*this); }
  #define MSTL_DEF_DUPLICATEIN(T) \
  void T::duplicateIn(void *space) const { new (space) T(*this); }
  #define MSTL_DECL_DUPLICATEIN(T) \
  void duplicateIn(void *space) const;

//external:
#define MSTL_IMPL_DUPLICATE(T) int sizeOf() const { return sizeof(T); }   MSTL_IMPL_DUPLICATEIN(T)
#define MSTL_DECL_DUPLICATE(T) int sizeOf() const;                        MSTL_DECL_DUPLICATEIN(T)
#define MSTL_DEF_DUPLICATE(T) int T::sizeOf() const { return sizeof(T); } MSTL_DEF_DUPLICATEIN(T)
#define MSTL_DEF_DUPLICATE_S(T,S) int T::sizeOf() const { return S; }     MSTL_DEF_DUPLICATEIN(T)
};

template<class S=Empty> class Copying
{
public:
   struct Dynamic
   {
      static S *duplicate(S *e) //dynamic copy of data
      {  return ( S *) e->duplicate();
      }
      template<class RS> struct Of: public Copying<RS>::Dynamic {};
   };
   struct Static
   {
      static S *duplicate(S *e) //static copy of data
      { return Create<S>::aNew(*e);
      }
      template<class RS> struct Of: public Copying<RS>::Static {};
   };
   struct NoCopy
   {
      static S *duplicate(S *e) //dynamic copy of data
      {  return 0;
      }
      template<class RS> struct Of: public Copying<RS>::NoCopy {};
   };
};

template<class S=Empty> class Counted: public S
{
public:
   int refcount;
   void share() { _ASSERT_VERBOSE(refcount>=0 && refcount<10000000,_TVAR(i,refcount);); refcount++; }
   bool unshare() {  _ASSERT_VERBOSE(refcount>0 && refcount<10000000,_TVAR(i,refcount);); return --refcount>0; }
   bool unique() {  _ASSERT_VERBOSE(refcount>=0 && refcount<10000000,_TVAR(i,refcount);); return refcount<2; }
   /// @precondition refcount==0
   Counted():S() { refcount = 0; }
   Counted(const S& cpyfrom):S(cpyfrom) { refcount = 0; }
   Counted(const Counted& cpyfrom):S(cpyfrom) { refcount = 0; }
};

//----- pointers -----

/// removes one level of two-level pointer safely (leaving zero pointer as zero pointer.)
//TT T *safeindirect(BasicPtr<T> *p) { return p ? (T *)*p : 0; }

#define PV this->d()

template<class T=Empty, typename CG=Copying<>::Static > struct Behaviour
{
public:
   /// basic pointer class without behaviour
   class BasicPtr: public CG::template Of<T>
   {
   protected:
      T *p;
      T &d() const { return *p; }
   public:
      void null() { p= 0; }
      bool valid() const { return p!=0; }
      bool isempty() const { return !valid(); }
      bool operator!() const { return !valid(); }
      T &operator*() const { return *p; }
      T *operator->() const { return p; }
      operator T *() const { return p; }
      operator const T *() const { return p; }
      T *&ptrRef() { return p; }
      bool operator==(const T *b) const { return p==b; }
      template<typename S> bool operator==(const S &b) const { return *p==b; }
      bool operator!=(const T *b) const { return p!=b; }
      bool operator!=(const T &b) const { return *p!=b; }
      bool operator>(const BasicPtr &b) const { return p>b.p; }
      bool operator>=(const BasicPtr &b) const { return p>=b.p; }
   };

   /// Referential pointer behaviour (see \ref Ptr).
   class Ref: public BasicPtr
   {
   protected:
      inline void erase() {this->p=0;}
      static inline void unuse(T *q) {}			
      void blindSet( T *q ) { this->p=q;}
      void copy( T *q ) { blindSet(q);}
      void set( T *q ) { blindSet(q); }
      void setCopy( T *q ) { blindSet(q); }
      void take( T *&q ) { blindSet(q); q=0; }
      void detach() { set (duplicate(this->p)); }
   public:
      template<class RT, class RCG> struct Of: public Behaviour<RT,RCG>::Ref {};
   };
   /// Private class: owning/autodeletion pointer behaviour (see \ref Ptr).
   class Own: public Ref
   {
   protected:
      static inline void unuse(T *q) { if (q!=0) freeObject(q); }			
      inline void erase() { T *op=this->p; this->p=0; unuse(op); }
      void copy( T *q ) { this->blindSet(q!=0?this->duplicate(q):0); }
      void set( T *q ) { T *op=this->p; this->blindSet(q); if (q!=op) unuse(op); }
      void setCopy( T *q ) { if (q!=this->p) unuse(this->p); copy(q); }
      void take( T *&q ) { T *oq=q; q=0; set(oq); } // must exactly be this
   public:
      template<class RT, class RCG> struct Of: public Behaviour<RT,RCG>::Own {};
   };
#if 000
   class GC: public Ref
   {
   protected:
      inline void erase() { T *op=this->p; if (op) {this->p=0; op->GCunuse(); } }
      static inline void unuse(T *q) { if (q) q->GCunuse(); }
      void set( T *q ) { if (q!=this->p) { T *op=this->p; this->blindSet(q); op->GCunuse(); } }
      void setCopy( T *q ) { set(q); }
   public:
      template<class RT, class RCG> struct Of: public Behaviour<RT,RCG>::GC {};
   };
#endif
   /** Private class: sharing/refcounting pointer behaviour(see \ref Ptr).
    *  Object must have share-, unshare- and unique-function.
    */
   class Share: public BasicPtr
   {
   protected:
      inline static void unuse( T *p) { if (p && !p->hdr.unshare()) freeObject(p); }
      inline void erase() { T *op=this->p; this->p=0; unuse(op); }
      void blindSet( T *q) { if (q) q->hdr.share(); this->p=q; }
      void copy( T *q ) { blindSet(q);}
      void set(T *q) { T *op=this->p; blindSet(q); unuse(op); }
      void setCopy( T *q ) { set(q); }
      void take(T *&q) { T *op=this->p; this->p=q; q=0; unuse(op); }
    public:
      template<class RT, class RCG> struct Of: public Behaviour<RT,RCG>::Share {};
      bool isunique() { return this->p->hdr.unique(); } 
      void detach() { if (this->p && !this->p->hdr.unique()) {this->set (this->duplicate(this->p));} }
   };
};

//template<class T, typename CG> void Behaviour<T,CG>::Share::erase( T *t) { if (t && !t->hdr.unshare()) freeObject(t); }

//declare:

template<typename C, class H, class B=Behaviour<>::Ref,class CG=Copying<>::Static > class HPtr;
/** Ptr<type, behaviour>
 * behaviour specifies how data pointed to is handled in case of 
 * creating pointer, deleting pointer, assigning pointer, etc.
 * See \ref Share,\ref Own and \ref Ref for three possible behaviours.
 */
template<typename T, class B=Behaviour<>::Ref,class CG=Copying<>::Static > class Ptr:
   public B::template Of< T, CG >
{
   typedef typename B::template Of< T, CG > Super;
protected:
   void blindtake(T *&q) { Super::blindSet(q); q=0; } //precondition: p=NULL
   void blindtake(Ptr &q) { Super::blindSet(q.p); q.p=0; } //precondition: p=NULL
public:
   Ptr( void *ptr) { Super::blindSet(const_cast<T *>((T *)ptr)); }
   Ptr() { Super::null(); }
   Ptr( const T *ptr) { Super::blindSet(const_cast<T *>(ptr) ); }
   Ptr( const Ptr &ptr) { Super::copy(ptr); }
   Ptr &operator=(T *q) { Super::set(q); return *this; }
   /// Non-const cast in necessary because shared object might change if it has a refcount.
   Ptr &operator=(const   T *q) { return operator=((T*)q);}
   Ptr &operator=(const Ptr &q) { Super::setCopy(q); return *this; }
   inline void erase() { Super::erase(); }
   inline ~Ptr() { erase(); }
   void create(int subclassSize=sizeof(T)) { Super::set(Create<T>::fromSpace( reserveBytes<T>(subclassSize) )); }
   inline static void erase(T *q) { Super::unuse(q); }
   void take(Ptr &q) { Super::take(q.p); }
   void blindset(T *q) { Super::blindSet(q); } //only use this when you know what you are doing
   T *take() { T *r=this->p; this->p=0; return r; }
   operator void *() const { return this->p; }
   typedef T Type;
   typedef T *TP;

   typedef  Ptr<T,            Behaviour<>::Ref  , CG                 > Ref;
   typedef  Ptr<T,            Behaviour<>::Own  , CG                 > Own;
   ///shared ownership pointer (with transparent refcount and reserve func).
   typedef HPtr<T, Counted<>, Behaviour<>::Share, CG                 > Share;
   ///ref pointer to object reserved with SHPTR(T).
   typedef HPtr<T, Counted<>, Behaviour<>::Ref  , CG                 > SRef;
   typedef  Ptr<T,            B,                  Copying<>::Dynamic > Dynamic;
   typedef  Ptr<T,            B,                  Copying<>::NoCopy  > NoCopy;
};

/** Header-Ptr<data, header, behaviour>
 *  Pointer that hides actual data-holder by representing it content(C).

 *  Use "new (hptr) C(...)" to create an object.
 */

template<typename C, class H, class B,class CG > class HPtr:
  public Ptr<Holder<C,H>,B,CG>
{
protected:
   C &d() const { return (C &)*(this->p); }
   typedef Ptr<Holder<C,H>,B,CG> Super;
public:
   HPtr() : Super() {}
   HPtr( const typename HPtr::TP ptr) : Super(ptr) {}
//   HPtr( const C &cpyfrom): Ptr<T,S>(new I(cpyfrom)) {}
  HPtr( const HPtr &ptr) : Super(ptr) {}
  explicit HPtr( const C *ptr)     : Super(ptr?(typename HPtr::TP)((char *)ptr+(sizeof(C)-sizeof(typename HPtr::Type))):0) {}
  explicit HPtr( void *ptr)        : Super(ptr) {}
   HPtr &operator=( const HPtr &ptr) { Super::operator=((const Super &)ptr); return *this; }
   C &operator*()   const { return PV; }
   C *operator->()  const { return &PV; }
      operator C*() const { return this->p?&PV:0; }
      operator const C*() const { return this->p?&PV:0; }
   /// returns unitialized C
   void *allocate(int subclassSize=sizeof(C))
   { Super::create( subclassSize-sizeof(C)+sizeof(typename HPtr::Type) );
     return (void *)&PV;
   }
   H &header() const { return this->p->hdr; }
   C *release() { header().unshare(); C *t = &PV; this->p = 0; return t; } 
   typename HPtr::TP releaseTP() { header().unshare(); typename HPtr::TP t = this->p; this->p = 0; return t; } 
   void create(int subclassSize=sizeof(C))
   {  Create<C>::fromSpace( allocate(subclassSize) );
   }
   inline ~HPtr() {}
#ifdef GCC_NEW
   #define HPTR_NEW(ptr, Class) new ((ptr).allocate(sizeof(Class))) Class
#else
   #define HPTR_NEW(ptr, Class) new (ptr) Class
   friend void * operator new  (size_t s, HPtr &alloc) { return alloc.allocate(s); }
   friend void * operator new[](size_t s, HPtr &alloc) { return alloc.allocate(s); }
#endif
   bool operator==(const C *b) const { return &PV==b; } // besides ==operators in BasicPtr class!
   bool operator==(const HPtr &b) const { return this->p==b.p; } // besides ==operators in BasicPtr class!

   typedef  HPtr<C, H        , Behaviour<>::Ref  , CG                 > Ref;
   typedef  HPtr<C, H        , Behaviour<>::Own  , CG                 > Own;
   ///shared ownership pointer (with transparent refcount and reserve func).
   typedef  HPtr<C, Counted<>, Behaviour<>::Share, CG                 > Share;
   ///ref pointer to object reserved with SHPTR(T).
   typedef  HPtr<C, Counted<>, Behaviour<>::Ref  , CG                 > SRef;
   typedef  HPtr<C, H        , B,                  Copying<>::Dynamic > Dynamic;
   typedef  HPtr<C, H        , B,                  Copying<>::NoCopy  > NoCopy;
};
#ifdef GCC_NEW
}
template<typename C, class H, class B,class CG > void * operator new  (size_t s, MSTL::HPtr<C,H,B,CG> &alloc) { return alloc.allocate(s); }
template<typename C, class H, class B,class CG > void * operator new[](size_t s, MSTL::HPtr<C,H,B,CG> &alloc) { return alloc.allocate(s); }
namespace MSTL {
#endif
///Fast Vector (inline expanded)
template<typename T, int S> struct FVec
{
   T e;
   FVec<T,S-1> n;
   FVec() {}
   FVec(const T *l): e(*l), n(l+1) {}
   FVec(const T &v): e(v), n(v) {}
   FVec(const FVec &f): e(f.e), n(f.n) {}
   FVec &operator=(const FVec &f) { e=f.e; n=f.n; return *this; }
   operator T *() { return (T *)this; }
   operator const T *() { return (T *)this; }
   T &operator[](const int &i) { return (i==0) ? e : n[i-1]; }
   const T &operator[](const int &i) const { return (i==0) ? e : n[i-1]; }
   T sum()    const { return e      + n.sum(); }
   T mul()    const { return e      * n.mul(); }
   T sumsqr() const { return e*e + n.sumsqr(); }
   T size()   const { return sqrt(sumsqr()); }
   FVec &normalise(T nsize=1) { nsize/=size(); (*this)*=nsize; return *this;}
   FVec &negate() { e = -e;     n.negate(); return *this; }
   FVec &abs()    { e = abs(e); n.abs(); return *this; }
   FVec &sqr()    { e *= e; n.sqr(); return *this; }
   ~FVec() {}
   #define OP(X) \
    FVec &operator X##=(const FVec &f) { e X##= f.e; n.operator X##=(f.n); return *this; }\
    FVec &operator X##=(const T &v) { e X##= v; n.operator X##=(v); return *this; } \
    FVec operator X(const FVec &f) const { return FVec(*this) X##= f; }\
    FVec operator X(const T &v) const { return FVec(*this) X##= v; }
   OP(+) OP(-) OP(/) OP(*) OP(<<) OP(>>) OP(^) OP(&) OP(|)
   #undef OP
};

template<typename T> struct FVec<T,1>
{
  T e;
  FVec() {}
  FVec(const T &l): e(l) {}
  FVec(const T *l): e(*l) {}
  FVec(const FVec &f): e(f.e) {}
  FVec &operator=(const FVec &f) { e=f.e; return *this; }
  T &operator[](const int &i) { return e; }
  const T &operator[](const int &i) const { return e; }
  T sum() const { return e; }
  T mul() const { return e; }
  T abs()    const { return abs(e) + this->n.abs(); }
  T sumsqr() const { return e*e; }
  void abs()    { e = abs(e); }
  void negate() { e = -e; }
  void sqr()    { e *= e; }
  void dec()    { e--; }
  void inc()    { e++; }
  void set(int i)    { e=i; }
  ~FVec() {}
  #define OP(X)\
    FVec &operator X##=(const FVec &f) { e X##= f.e; return *this; }\
    FVec &operator X##=(const T &v) { e X##= v; return *this; }\
    FVec operator X(const FVec &f) const { return FVec(e X f.e); } \
    FVec operator X(const T &v) const { return FVec(e X v); }
   OP(+) OP(-) OP(/) OP(*) OP(<<) OP(>>) OP(^) OP(&) OP(|)
   #undef OP
};

//-------- Vector ---------

template<typename T, class H> class GridData
{
public:
   H hdr;
private:
   char dat[1];
protected:
   T &item(int i) const { return ((T *)dat)[i]; }
public:
   operator T *() { return (T *)dat; }
   operator const T *() { return (T *)dat; }
   int length() { return hdr.mul(); }
   int sizeOf() { return sizeof(H)+sizeof(T)*length(); }
   void truncate(int newLen);
   void *duplicateIn(void *p);
   void *duplicate() { void *p=reserveBytes<GridData>(sizeOf()); duplicateIn(p); return p; }
   ~GridData();
   //GridData(H &cpyFrom): Holder<T,H>(cpyFrom) {}
   GridData() {}
};

template<typename T, class H> void *GridData<T,H>::duplicateIn(void *p)
{ int l=length();
  Create<H>::fromSpace(p, hdr);
  T *dp=(T *)((H *)p+1);
  while (--l>=0)
     Create<T>::fromSpace(dp+l, item(l) );
  return p;
}

template<typename T, class H> GridData<T,H>::~GridData() {  for (int l=length();--l>=0;) item(l).~T(); }

template<typename T, class H> void GridData<T,H>::truncate(int newLen)
{ for (int l=length();--l>=newLen;) item(l).~T();
	hdr.set(newLen); 
}

/** generic x-dimensional Matrix. 
 * Owner of header+dataset, where size of dataset is stored in the header.
 */

template <class T, class Header, class U=typename Ptr<GridData<T,Header> >::Own > class Grid: public U::Dynamic
{  
	void create(const Header &h)
	{ U::Dynamic::create( sizeof(Header)+sizeof(T)*h.mul() );
	 PV.hdr=h;
	}
public:
	Grid(const Grid &grid):U::Dynamic(grid) {} // makes a copy by dynamic mechanism
	Grid(const Header &h):U::Dynamic() { create(h); }
	operator T *() const { return (T *)PV; }
	operator const T *() const { return (T *)PV; }
	T &operator[](int i) const { return ((T *)(*this))[i]; }
	void *space(int i=0) const { return (void *)&((*this)[i]);}
	int length() const { return PV.length(); }
	TS int findIndex(const S &e) { int i=length(); while(--i>=0 && !(e==this->operator[](i))); return i; }
	TS int findIndexForward(const S &e) { int l=length(), i=0; while(i<l && !(e==this->operator[](i))) i++; return i; }
	void decLengthWithoutDestroy() { PV.hdr.dec(); }
	void truncate(int newLen) { PV.truncate(newLen); } // does destroy surplus elements! newLen must be smaller than current len
	void erase() { truncate(0); }
	void growByRealloc(const Header &newSize) {
		Grid g(newSize);
		memcpy(g.space(),space(),PV.sizeOf());
		PV.hdr.set(0); // prevents destruction of objects
		this->take(g);
   }
   void init(const int &i, const T &copyfrom)
   { Create<T>::fromSpace(space(i),copyfrom); }
   Grid(const Header &h, const T &copyfrom):U::Dynamic()
   { create(h); for(int i=length(); --i>=0;) init(i, copyfrom); }
   ~Grid() {}
   void init() { for(int i=length(); --i>=0;) Create<T>::fromSpace(space(i)); }
   void hardcopy(const T *from) { memcpy(space(), from, length()*sizeof(T)); }
   void hardcopy(const T *a, int lena, const T *b)
   {  memcpy(space(), a, lena*sizeof(T));
      memcpy(space(lena), b, (length()-lena)*sizeof(T));
   }
   typedef Grid<T, Header, typename U::Share > Share;
   typedef Grid<T, Header, typename U::Ref > Ref;
   bool operator!() const { return length()==0; }
};

template<typename T, class U = Grid<T,FVec<int,1> > > class Vector: public U
{
public:
  Vector(const U &cpyfrom): U(cpyfrom) {}
   //Vector(typename U::Type *p): U(p) {}
  Vector(int length=0): U(FVec<int,1>(length)) {}
  Vector(int length, const T &copyfrom): U(FVec<int,1>(length), copyfrom) {}
  ~Vector() {}
  typedef Vector<T, typename U::Ref > Ref;
  typedef Vector<T, typename U::Share > Share;
};

#define U Vector<char>::Share
/// Easy&Fast String type with automatic char * conversion and automatic garbage collection.
class String: public U
{
  typedef U Parent;
public:
  // use detach() to make string indepedent
  int strlen() const { return ::strlen(*this); }
  int length() const { return Parent::length()-1; }
  String(int length=0):                   U(length+1)               {(*this)[length]=0;}
  String(const String &s):                U( s )                  {}
  String(const char *s):                  U( ::strlen(s)+1 )               { hardcopy(s); }
  String(const char *s, int l):           U( l+1 )                         { hardcopy(s); (*this)[l]=0; }
  String(const String &a,const char *b):  U( a.length()+ ::strlen(b)+1   ) { hardcopy( a, a.length(), b );  }
  String(const String &a,const String &b):U( a.length()+b.length()+1     ) { hardcopy( a, a.length(), b );  }
  String(const char *a,  const String &b):U( ::strlen(a) +b.length()+1   ) { hardcopy( a, ::strlen(a),  b );  }
  String(const char *a,  const char *b):  U( ::strlen(a) + ::strlen(b)+1 ) { hardcopy( a, ::strlen(a),  b );  }
  String &operator=(const char *s) { U::operator=(String(s)); return *this; }
  static String create(int buf, const char *format,...);
  String &operator=(const String &s) { U::operator=(s); return *this; }
  String operator+(const char *s) { return String(*this,s); }
  String operator+(const String &s) { return String(*this,s); }
  friend String operator+(const char *a, const String &b) { return String(a,b); }
	bool operator!() const { return (*this)[0]==0; }
  //char &operator[](int i) { return U::operator[](i); }
  String subset(int pos, int len);
  String subset(int pos) {  return subset(pos, length()-pos); }
	unsigned int hash() const
	{ const unsigned char *sp=(const unsigned char *)(const char *)*this;
	  unsigned int i=0;
	  while(*sp) i=(i<<1)^*(sp++);
	  return i;  
	}
  operator unsigned char *() const { return (unsigned char *)(char *)*this; }
  ~String() {}
  int strcmp(const String &b) const;
  #define SOP(x) \
  bool operator x(const String &b) const { return strcmp(b) x 0; }
  SOP(==) SOP(!=) SOP(>) SOP(>=) SOP(<) SOP(<=)
  #undef SOP
  #define FOREACHCHAR(s,i) for(char *i=s, *i##_end=i+s.length();i!=i##_end;i++)
  #define FOREACHUCHAR(s,i) for(unsigned char *i=s, *i##_end=i+s.length();i!=i##_end;i++)
};
#undef U

template<typename T, class U = Grid<T, FVec<int,2> > > class Matrix: public U
{
public:
   Matrix(typename U::Type *p): U(p) {}
	 Matrix(): U(FVec<int,2>(0)) {}
   Matrix(int s[2]): U(FVec<int,2>(s)) {}
   Matrix(int s[2], const T &copyfrom): U(FVec<int,2>(s), copyfrom) {}
   ~Matrix() {}
   inline T *operator[](int i) const
   {  return &U::operator[](i*PV.hdr[1]);}
   inline int rows() const { return PV[0]; }
   inline int cols() const { return PV[1]; }
   typedef Matrix<T, typename U::Ref > Ref;
   typedef Matrix<T, typename U::Share > Share;
};

template<typename T, class U = Grid<T,FVec<int,3> > > class Matrix3d: public U
{
public:
  Matrix3d(typename U::Type *p): U(p) {}
  Matrix3d(int size[3]): U(FVec<int,3>(size)) {}
  Matrix3d(int size[3], const T &copyfrom): U(FVec<int,3>(size), copyfrom) {}
  ~Matrix3d() {}
  inline T *index(int a, int b) const
  {  return &U::operator[]( (a+b*PV[2])*PV[1] );
  }
  inline T &index(int a, int b, int c) const
  {  return U::operator[]( a+(b+c*PV[2])*PV[1] );
  }
  inline int dimsize(int i) const { return PV[i]; }
  typedef Matrix3d<T, typename U::Ref > Ref;
  typedef Matrix3d<T, typename U::Share > Share;
};

struct QueueHdr: public FVec<int,1>
{ int getp, putp;
  bool full;
  QueueHdr(int l): FVec<int,1>(&l) {}
  QueueHdr(): FVec<int,1>() {}
};

/// queue functionality in Vector with a maximum size.

TT class VectorQueue: public Grid<T, QueueHdr>
{
public:
   int count() const
   {	int l=this->length();
			if (PV.hdr.full || !l) return l; else return (PV.hdr.putp-PV.hdr.getp+l)%l;
   }
   void clear() { PV.hdr.getp=PV.hdr.putp=0; PV.hdr.full = false; }
   VectorQueue(int length): Grid<T,QueueHdr>(QueueHdr(length)) { clear(); }
   bool isfull() {  return PV.hdr.full; }
   T &operator[](const int &a)
   {  return Grid<T,QueueHdr>::operator[]((a+PV.hdr.getp)%this->length()); }
   T &first() { return Grid<T,QueueHdr>::operator[](PV.hdr.getp); }
   void *put()
   {  void *p=this->space(PV.hdr.putp); PV.hdr.putp = (PV.hdr.putp+1) % this->length();
      if (PV.hdr.putp == PV.hdr.getp) PV.hdr.full = true;
      return p;
   }
   void put(const T& ce) { new (put()) T(ce); }
   T &unput()
   { T &e=(*this)[PV.hdr.putp];
     PV.hdr.putp = (PV.hdr.putp + this->length() -1) % this->length();
     PV.hdr.full = false;
     return e;
   }
   T &get()
   { T &c=first(); PV.hdr.getp = (PV.hdr.getp+1) % this->length(); PV.hdr.full = false; return c;}
   ~VectorQueue();
};

TT VectorQueue<T>::~VectorQueue()
{	
	if (!PV.hdr.full)
	{	for(int i=count(); --i>=0;)
		{	operator[](i).~T();
		}
		PV.hdr=0;
	}
}

//----- Functors -----

template<typename A, typename R=void > class Functor
{ 
public:
   virtual void doit(A a) {}
   virtual R funcit(A a) const { return R(); }
};

/// Functor with functionpointer.
template<typename A, typename R = void > class Func: public Functor<A,R>
{ 
public:
   R (*func)(A);
   Func( R (f)(A)): func(f) {}
   void doit(A a) { func(a); }
   R funcit(A a) const { return func(a); }
};

template<typename A > class GreaterFc: public Functor<A,bool>
{ 
public:
   A m_v;
   GreaterFc( const A v ): m_v(v) {}
   bool funcit(A a) const { return a > m_v; }
};

/// Functor with functionpointer and extra parameter for this function.
template<typename A, typename P, typename R=void > class PFunc: public Functor<A,R>
{ 
   P param;
public:
   R (*func)(A,P);
   PFunc( R (f)(A,P), P p): func(f), param(p) {}  
   virtual void doit(A a) { func(a,param); }
   virtual R funcit(A a) { return func(a,param); }
};

template<typename A, typename B=A, typename R=void > class Functor2
{
public:
   virtual void doit(A a, B b)=0;
   virtual R funcit(A a, B b)=0;
};

template<typename A, typename B=A, typename R=void > class Func2: public Functor2<A,B,R>
{
public:
   R (*func)(A,B);
   Func2( R (f)(A,B)): func(f) {}
   virtual void doit(A a, B b) { func(a,b); }
   virtual R funcit(A a, B b) { return func(a,b); }
};

template<typename A, typename B, typename P, typename R=void > class PFunctor2: public Functor2<A,B,R>
{ 
   P param;
public:
   R (*func)(A,B,P);
   PFunctor2( R (f)(A,B,P)): func(f) {} 
   virtual void doit(A a, B b) { func(a,b,param); }
   virtual R funcit(A a, B b) { return func(a,b,param); }
};

//----- List -----

/**
 *  List = owner of first Node OR owns nothing.
 *  A List is defined recursively (see definition of Node).
 *  The "operator->" fetches the data directly while hiding the
 *  nodes themselves (List is derived from RPTR<...>).
 *  No two lists can point to the same Node. 
 *  There is a copy constructor which make duplicates of the
 *  nodes, while most other function just capture nodes from another List 
 *  or from another position in the same List.<p>
 *  Use: "new (List)T(..);" to prepend a new element at begin of List.
 *  <p><p>
 *  <b>List example</b><p> \verbatim  
 *             ___     ___
 * list = o-->|  o+-->|  o+--> NULL
 *            |_m_|   |_m_|
 *              |       |
 *             \|/     \|/
 *            elem1   elem2
 *
 * where every "o" and "m" are aggregation relationships, but m indicates a
 * real member while o indicates a owning pointer (OPTR).
 *\endverbatim
 */

TT class List;

TT class List: public HPtr<T, List<T>, Behaviour<>::Own >
{
public:
   /// Iter = iterator over elements
   class Iter: public HPtr<T, List<T> >//::Ref pointer
   {
     using HPtr<T, List<T> >::p;
   public:
      Iter next() const { return p->hdr.p; }
      Iter &operator++() { p = p->hdr.p; return *this; }
      Iter &operator++(int) { ++(*this); return *this; }

      Iter(const List &l): HPtr<T, List<T> >(l.p) {}
      Iter(const Iter &l): HPtr<T, List<T> >(l) {}
      Iter(void *p=0):  HPtr<T, List<T> >(p) {}
	  explicit Iter(const T *p): HPtr<T, List<T> >(p) {}
      List<T> &list() const { return p->hdr; }
   };
	using HPtr<T, List<T>, Behaviour<>::Own >::p;

#define BFST(a) bool (a)(const T&, S)
#define VFST(a) void (a)(const T&, S)
#define VFST2(a) void (a)(const T&, const T&, S)

   friend class Iter;
public:
//--- browsing using parameterized functions ---
   int      locateindex(const Functor<const T &,bool> &f) const;
   List&    locate     (const Functor<const T &,bool> &f) const;
   T*       locatedata (const Functor<const T &,bool> &f) const;
   template<typename C>
      List& search (const T &v) const { return locate( C(v) ); }
   List&    search (const T &v) const { return search<GreaterFc<const T &> >(v); }
   void     foreach    (const Functor<T&> &f) const;
   void     foreach    (const Functor<const T&> &f)   const { foreach((const Functor<T&>) f); }
   void     foreachpair(const Functor2<T &> &f) const;
   void     foreachpair(const Functor2<const T &> &f) const { foreachpair((const Functor2<T &>) f); }
//--- browsing nodes: ---
   List&    end() const;
   List&    last() const;
   List&    next() const { return p->hdr; }
   List&    next(int i) const;
   /// pointer to element i. Null if i>=length.
   T *      pnext(int i=1) const;
   T *      plast() const;
   T &      operator[](int i) const { return *pnext(i); }
   //const T &operator[](int i) const { return *pnext(i); }
   T &      lastdata() const { return *plast(); }
   TS List& find(const S &e) const;
   TS bool  contains(const S &e) const;
   TS T *   finddata(const S &e) const;
   TS int   findindex(const S &e) const;
   int      length() const;
//--- removing, prepending, reposition and taking of first Node(s): ---
            inline List() {}
   /// take a number of nodes which replace the current list
   void     takeset(List &from, int count) // take-over a portion
                 { this->take(from); from.blindtake(next(count)); }
   void     takeone(List &from) { this->take(from); from.blindtake(next()); }
   void     removeone() { this->take(next()); }
   void     removeset(int count) { this->take(next(count)); } 
	 void     erase();// use erase() to remove all
//   void *   prependalloc(int subclassSize) { typename List::Type *op=p; p=0; this->allocate(subclassSize); next().p=op; return p->space(); }
   void *   prependalloc(int subclassSize=sizeof(T))
	 { typename List::Type *op=p; p=0; this->allocate(subclassSize); next().p=op; return p->space(); }
#ifdef GCC_NEW
   #define LIST_NEW(list, Class) new ((list).prependalloc(sizeof(Class))) Class
#else
   #define LIST_NEW(ptr, Class) new (ptr) Class
   friend void * operator new(size_t s, List &alloc) { return alloc.prependalloc(s); }
#endif
   TS T&    prepend(const S &e) { LIST_NEW(*this,T)(e); return **this; }
   T&       prepend() { LIST_NEW(*this, T)(); return **this; }

   /// take and prepend at beginning of list
   void     takeprependall(List &from) { from.end().take(*this); this->take(from); }
   void     takeprependset(List &from, int count);
   /// faster than takeprependset with count=1.
   void     takeprependone(List &from) { typename List::Type *op=p; p = from.p; from.p=next().p; next().p=op; }

   void inverse();
//--- sorting : ---
   template<typename C>
     void  takeinsortone(List &from ) // takes one and insert sorted
      { List l; l.takeprependone(from); search<C>(*l).takeprependall(l);  }
   void     takeinsortone(List &from) const { takeinsortone<GreaterFc<const T &> >(from); }
   template<typename C>
   void     sortone() { takeinsortone<C>(*this);  }
   void     sortone() { sortone<GreaterFc<const T &> >();  }
//--- sorting ---
//#define BFPARAM(S) bool(*until) (const T&, S) =stdUntil<S>
//#define BFPRMT BFPARAM(const T&)
//#undef BFPARAM
//#undef BFPRMT
   #define FOREACH(lt, l, i) for (lt::Iter i(l); !!i; i++)
   #define FOREACHP(lt, p, i) for (lt::P i(p); !!*i; i++)
   #define FOREACHT(lt, l, i) FOREACH(typename lt,l,i)
   #define FOREACHPT(lt, p, i) FOREACHP(typename lt,p,i)

            List(const List &cpyfrom);
            List(const List &cpyfrom, int count);
            ~List() { erase(); } // this destructor is necessary to prevent stack recursion
   List& operator=(const List &cpyfrom);
//--- typedefs and friend functions ---

   /// reflist: uses ref pointer to object instead of owning object in a Node.
   typedef List< Ptr< T > > Ref;
   /** ownlist: uses owning pointer instead of owning object in a node directly.
    *  this way subclasses can also be added in list.<p>
    *  NOTE: beware of difference between takeprepend and prepend (which uses copy-constructor!)
    */
   typedef List< typename Ptr< T >::Own > Own;
   typedef List< typename Ptr< T >::Share > Share;
   typedef Ptr< List > P;

   friend P &operator++(P &p) { p = ( &(p -> next()) ); return p; }
   friend P &operator++(P &p, int) { operator++(p); return p; }

private:
   TS static void cpyfunc(const T &ce, const S &arg, void *mem) { new (mem) T(ce,arg); }
};

#ifdef GCC_NEW
}

TT void * operator new(size_t s, MSTL::List<T> &alloc) { return alloc.prependalloc(s); }

namespace MSTL {
#endif

//----- implementation of complex functions -----

TT void List<T>::takeprependset(List &from, int count)
{  //typename List::Type *op=p; p = from.p; List &l=from.next(count); from.p=l.p; l.p=op;
    List &l=from.next(count); List t; t.blindtake(l); l.blindtake(*this);
    blindtake(from); from.blindtake(t);
}

TT List<T>& List<T>::operator=(const List &cpyfrom)
//{ erase(); return *Create<List>::fromSpace(this,cpyfrom); }
{ this->erase(); 
   P to(this); FOREACHT(List,cpyfrom,i) { to->prepend(*i); to++; }
   return *this;
}

TT void List<T>::erase()
{ while (p)
  { typename List::Type *op=p;
		p=op->hdr.take();
	  HPtr<T, List<T>, Behaviour<>::Own >::erase(op);
  }
}
TT T* List<T>::locatedata(const Functor<const T &,bool> &f) const
{ FOREACHT(List,*this,i) if (f.funcit(*i)) return i; return 0;}

TT List<T>& List<T>::locate(const Functor<const T &,bool> &f) const
{  P i(this); while((!!*i) && !f.funcit(**i) ) i++; return *i;}

TT int List<T>::locateindex(const Functor<const T &,bool> &f) const

{ int i=0; for ( Iter j(p); !!j && !f.funcit(*j); j++) i++; return i; }

TT void List<T>::foreach(const Functor<T&> &f) const { FOREACHT(List,*this,j) f.doit(*j); }

TT void List<T>::foreachpair(const Functor2<T &> &f) const
{  Iter i(p);
   if (!!i)
   {  for(Iter oi(i);;oi=i)
    {  i++; if (!i) break;
         f.doit(*oi, *i);
    }
   }
}

TT TS List<T>&  List<T>::find(const S &e) const { P i(this); while(!!*i && !(e==**i)) i++; return *i;}
TT TS bool  List<T>::contains(const S &e) const { FOREACHT(List,*this,i) if (e==*i) return true; return false;}

TT TS int    List<T>::findindex(const S &e) const
{ int i=0;
  Iter j(*this);
  while(true)
  { if (!j)     return -1;
    if (e==*j)  return i;
    j++; i++;
  }
}

TT TS T *    List<T>::finddata(const S &e) const { Iter i(p); while(!!i && !(e==*i)) i++; return (T *)i;}
TT int       List<T>::length() const{ int c=0; FOREACHT(List,*this,i) c++; return c;}
TT List<T>&  List<T>::next(int i) const  { P j(this); while(--i>=0 && !!*j) j++; return *j;}
TT T *       List<T>::pnext(int i) const { FOREACHT(List,*this,j) if(--i<0) return j; return 0;}
TT List<T>&  List<T>::end() const        { P e(this); while(!!*e) e++; return *e; }
TT List<T>&  List<T>::last() const        { P i(this); if (!!*i) while(!!i->next()) i++; return *i; }
TT T *       List<T>::plast()       const { Iter e(p), l; while(!!e) {l=e;e++;} return l; }

TT  List<T>::List(const List<T> &cpyfrom)
{ P to(this); FOREACHT(List,cpyfrom,i) { to->prepend(*i); to++; }
}

TT List<T>::List(const List<T> &cpyfrom, int count)
{  P to(this);
   for(Iter from(cpyfrom);!!from && --count>=0; from++, to++)
      to->prepend(*from);
}

TT void List<T>::inverse()
{ List l;
  while (!!*this) l.takeprependone(*this);
  this->blindtake(l);
};

//_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._.

/** 
 * Save Reference to object.
 * every object gets an unique ticket number (of integer type ID)
 * a list is kept to store all living (ID,object) pairs
 */
template<typename TYPE, typename ID=int > class SaveRef
{

#define S SaveRef<TYPE, ID>
public:
   static ID add(TYPE *s)
   {  return ( new (sm_refs.prependspace())S(s) ) ->m_id;
   }
   static TYPE *remove(ID id)
   {  for (typename List<S>::P i(&sm_refs); !!*i; i++) 
      {  if ( (*i)->m_id == id )
         {  TYPE *o = (*i)->m_s;
            i->remove();
            return o;
         }
      }  
      return NULL;
   }
   static TYPE *find(ID id)
   {  for (typename List<S>::Iter i(sm_refs); !!i; i++)
      {  if ( i->m_id == id ) return i->m_s;
      }  
      return NULL;
   }

   static bool refExistance() { return sm_refs.valid(); }
private:
   S(TYPE *s)
   {  while (find(sm_nextId)!=0) sm_nextId++; // extra safety after Id overflow ;-)
      m_s = s;
      m_id = sm_nextId;
      sm_nextId++; 
   }
   TYPE *m_s;
   ID m_id;
   static List<S> sm_refs;
   static ID sm_nextId;
};

/// non-zero startnumber as first number
template<typename TYPE, typename ID> ID S::sm_nextId = 42;
template<typename TYPE, typename ID> List<S> S::sm_refs;
#undef S

//---------------------------------------------------

/// simple checksum function, useable for debugging and testing.

TT T xorSum(const unsigned char *buf, int len)
{
   T sum = 0;
   for(int i=len/sizeof(T); --i>=0;)
   {  sum ^= *(T *)buf;
      buf += sizeof(T);
   }
   return sum;
}

//---------------------------------------------------
template<typename OT, OT SIZE, typename ST=OT> struct SplitNum
{  
#define P SplitNum<OT,SIZE,ST>
   ST segment;
   OT offset;
   TS P(S num): segment(num / SIZE), offset(num % SIZE) {}
   ST segmentCount(const P &end) const
   {  return end.segment - segment;
   }
   /** gives the usage in bytes of current position until end of this segment or
    * if segment of "end" is reached, the difference between "end" and current.
    */
   OT segmentUsage(const P &end) const
   {  return ( isLast(end) ? end.offset : SIZE ) - offset;
   }
   bool isLast(const P &end) const
   {  return segment == end.segment;
   }
   TS void operator+=(S num)
   {  segment += (num + offset) / SIZE;
      offset = (num + offset) % SIZE;
   }
   bool isAligned() const
   { return offset == 0;
   }
#undef P
};

#undef TT
#undef TS

template<class T, int Size> class Hash
{
  List<T> m_hash[Size];
public:
  enum { size = Size };
  Hash() {}
  template<typename S> T *find(const S &s) { return getList(s).finddata(s);  }
  template<typename S> T &findOrInsert(const S &s) 
	{ List<T> &lst=getList(s);
		T *l=lst.finddata(s);  
		if (l) return *l;
		return s.duplicateIn(lst);
	}
  template<typename S> void remove(const S &s) 
	{ getList(s).find(s).removeone();
	}
  template<typename S> List<T> &getList(const S &s) { return m_hash[s.hash()%Size]; }
  List<T> *getLists() { return m_hash; }
  typedef T Type;
};

template<typename T, typename I> Holder<T,I>::~Holder() { ((T *)dat)->T::~T(); }

}

#endif /* __MSTL_H__ */

